package written_examination_questions;

import java.util.ArrayList;
import java.util.List;

public class Demo20251110 {
    /**
     * 按奇偶排序数组
     * @param nums
     * @return
     */
    public int[] sortArrayByParity(int[] nums) {
        int n = nums.length, left = 0, right = n - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 == 0) {
                left++;
            }
            while (left < right && nums[right] % 2 == 1) {
                right--;
            }
            if (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
        return nums;
    }

    private void swap(int[] nums, int left, int right) {
        int tmp = nums[left];
        nums[left] = nums[right];
        nums[right] = tmp;
    }

    /**
     * 找到字符串中的所有字母异位词
     * @param ss
     * @param pp
     * @return
     */
    public List<Integer> findAnagrams(String ss, String pp) {
        List<Integer> ret = new ArrayList<>();
        char[] s = ss.toCharArray();
        char[] p = pp.toCharArray();

        // hash1用来统计字符串p中每一个字符出现的个数
        int[] hash1 = new int[26];
        for (char ch : p) {
            hash1[ch - 'a']++;
        }

        // hash2用来统计窗口中每一个字符出现的个数
        int[] hash2 = new int[26];

        int m = p.length; // p中字符的个数
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            if (++hash2[in - 'a'] <= hash1[in - 'a']) {
                // 进窗口  维护count
                count++;
            }
            // 判断   如果长度超过p的长度了，则出窗口
            if (right - left + 1 > m) {
                char out = s[left++];
                // 出窗口
                if (hash2[out - 'a']-- <= hash1[out - 'a']) {
                    count--;
                }
            }
            // 更新结果
            if (count == m) {
                ret.add(left);
            }
        }
        return ret;
    }


    /**
     * 复习
     */
    // 最小覆盖子串
    public String minWindow(String ss, String tt) {
        char[] s = ss.toCharArray();
        char[] t = tt.toCharArray();

        // 创建一个 Hash 表保存 t 的字符种类和个数
        int[] hash1 = new int[128];
        int kinds = 0; // 记录 t 中字符的种类
        for (char ch : t) {
            if (hash1[ch]++ == 0) kinds++;
        }

        // 再创建一个 Hash 表记录进窗口的元素种类和数量 count 表示的是窗口中出现的t中元素的种类
        int[] hash2 = new int[128];
        int minLen = Integer.MAX_VALUE, begin = -1; // 记录起始位置和长度
        for (int left = 0, right = 0, count = 0; right < s.length; right++) {
            char in = s[right];
            // 进窗口
            hash2[in]++;
            if (hash2[in] == hash1[in]) count++;
            // 判断
            while (count == kinds) {
                // 更新结果
                if (right - left + 1 < minLen) {
                    begin = left;
                    minLen = right - left + 1;
                }
                // 出窗口
                char out = s[left];
                left++;
                if (hash2[out] == hash1[out]) { // 如果窗口中的该元素数量与t字符串中该元素数量相同，那么钙元素出窗口后，窗口中元素种类-1
                    count--;
                }
                hash2[out]--;
            }
        }
        if (begin == -1) return new String();
        else return ss.substring(begin, begin + minLen);
    }

    // 反转字符串
    public void reverseString(char[] s) {
        int left = 0, right = s.length - 1;
        while (left <= right) {
            char tmp = s[left];
            s[left] = s[right];
            s[right] = tmp;
            left++;
            right--;
        }
    }

    // 合并两个有序数组
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (nums2[j] >= nums1[i]) {
                nums1[k] = nums2[j];
                j--;
            } else {
                nums1[k] = nums1[i];
                i--;
            }
            k--;
        }

        // i 遍历完了
        while (j >= 0) {
            nums1[k] = nums2[j];
            j--;
            k--;
        }
    }
}

/**
// LRU缓存
class LRUCache {

    public HashMap<Integer, Node> map; // 使用Map保存数据
    public Node head; // 头结点连接最近使用的节点
    public Node tail; // 尾节点连接最少使用的节点
    public int capacity; // 缓存容量
    public int size;

    public LRUCache(int capacity) {
        this.map = new HashMap<>();
        this.head = new Node(-1, -1);
        this.tail = new Node(-1, -1);
        // 连接上
        head.next = tail;
        tail.prev = head;
        this.capacity = capacity;
        this.size = 0;
    }

    public int get(int key) {
        if (!map.containsKey(key)) {
            return -1;
        }
        Node node = map.get(key);
        // 最近被访问的元素要加入到头结点之后，所以要先删除掉再加入到头结点后
        removeNode(node);
        addHead(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (map.containsKey(key)) { // 存在
            Node node = map.get(key);
            node.value = value; // 如果存在则覆盖值
            removeNode(node);
            addHead(node);
        } else { // 不存在
            // 缓存满了
            if (size >= capacity) {
                // 删除最少使用的节点
                Node last = tail.prev;
                removeNode(last);
                map.remove(last.key);
                size--;
            }
            // 缓存没满
            Node newNode = new Node(key, value);
            map.put(key, newNode);
            addHead(newNode);
            size++;
        }
    }

    // 加入到头节点之后
    private void addHead(Node node) {
        node.next = head.next;
        node.prev = head;
        head.next.prev = node;
        head.next = node;
    }

    // 删除节点
    private void removeNode(Node node) {
        node.prev.next = node.next;
        node.next.prev = node.prev;
    }
}

// 定义链表节点
class Node {
    int key;
    int value;
    Node next;
    Node prev;

    public Node(int key, int value) {
        this.key = key;
        this.value = value;
    }
}
*/